/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
    // vector<int> nums;
    // void dfs1(TreeNode *root)
    // {
    //     if(root == nullptr)
    //         return;
    //     dfs1(root->left);
    //     nums.push_back(root->val);
    //     dfs1(root->right);
    // }

    int ret = INT_MAX, prev = -1;
    void dfs2(TreeNode *root)
    {
        if(root == nullptr)
            return;
        
        dfs2(root->left);
        if(prev != -1)
            ret = min(root->val - prev, ret);
        prev = root->val;
        dfs2(root->right);
    }
public:
    int getMinimumDifference(TreeNode* root) {
        // 题目中说明是二叉搜索树，所以中序遍历就是有序的
        // 存入数组中，即可查找最小差值，由于是有序的，所以最小差值肯定在相邻元素之间
        // 下面这种解法是使用了额外数组，其实可以使用边遍历边记录的方式
        // dfs1(root);
        // int n = nums.size();
        // if(nums.size() < 2)
        //     return 0;
        // int ret = INT_MAX;
        // for(int i = 1; i < n; i++)
        //     ret = min(ret, nums[i] - nums[i - 1]);
        // return ret;

        dfs2(root);
        return ret;
    }
};